{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Transport Planning\n", "A firm must transport machines from production plants A, B and C to warehouses X, Y and Z. Five machines are required in X, 4 in Y and 3 in Z, whereas 8 machines are available in A, 5 in B and 3 in C. The transport costs (in euros) between sites\n", "are provided in the table below.\n", "\n", "| Plant/Warehouse | X | Y | Z |\n", "|-----------------|----|----|----|\n", "| A | 50 | 60 | 30 |\n", "| B | 60 | 40 | 20 |\n", "| C | 40 | 70 | 30 |\n", "\n", "**a)** Formulate an integer linear programming model that minimizes transport costs.\n", "This is a simple transportation problem, where the objective is to minimize the transportation costs. Let us note the \n", "transportation costs from plant $i$ to warehouse $j$ as $c_{ij}$, our model is: \n", "\n", "**Indices**\n", "\n", "- $i$ Production plants, $i \\in [A,B,C]$\n", "\n", "- $j$ warehouses, $j \\in [X,Y,C]$\n", "\n", "**Decision variables**\n", "\n", "- $x_{ij}$ (Integer) Number of machines to transport from production plant $i$ to warehouse $j$\n", "\n", "**Objective function**\n", "\n", "$z = \\sum_i{\\sum_j{c_{ij}*x_{ij}}}$\n", "\n", "**Constraints**\n", "Demand constraint\n", "\n", "$\\sum_i{x_{ij}} \\geq d_j \\quad \\forall j$\n", "\n", "\n", "**b)** Assume that the cost of transporting a machine from plant B increases by €10 for all the machines as of the third one; that is, the 4th, the 5th, etc. Reformulate the model in Section a) by considering this assumption.\n", "In this case, we need to define a new decision variable to factor in the extra costs incurred if we source more than \n", "three machines from plant B. Let us note these new decision variables as $x*_{Bj}$ and represents the machines that are \n", "sourced from factory B from the third machine. Le us also note as $c*_{Bj}$ the additional costs incurred from the third\n", "machine:\n", "\n", "| Plant/Warehouse | X | Y | Z |\n", "|-----------------|----|----|----|\n", "| B | 70 | 50 | 30 |\n", "\n", "Now, our problem model becomes:\n", "\n", "**Decision variables**\n", "\n", "- $x_{ij}$ (Integer) Number of machines to transport from production plant $i$ to warehouse $j$\n", "\n", "- $x*_{Bj}$ (Integer) Number of machines to transport from production plant B to warehouse $j$ from the third one\n", "\n", "- $Y$ (Binary) Used to determine whether the number of machines sourced from B is greater than 3.\n", "\n", "**Objective function**\n", "\n", "$z = \\sum_i{\\sum_j{c_{ij}*x_{ij}}} + \\sum_j{c*_{Bj}*x*_{Bj}}$\n", "\n", "\n", "**Constraints**\n", "Demand constraint\n", "\n", "$\\sum_i{x_{ij}} + x*_{Bj} \\geq d_j \\quad \\forall j$\n", " \n", "Logical constraints\n", "$\\sum_j{x_{Bj}}\\leq 3$\n", "\n", "$\\sum_j{x_{Bj}} - 3 + M*Y \\geq 0$\n", "\n", "$x*_{Bj} + M*Y \\geq 0 \\quad \\forall j$\n", "\n", "$x*_{Bj} \\leq M*(1-Y) \\quad \\forall j$\n", "\n", "Where M is a very large number. \n", "To explain the introduction of the binary decision variables and the set of constraints, note that what we want to \n", "accomplish is the following logic:\n", "\n", "\"if $\\sum_j{x_{Bj}}=3$ then $x*_{Bj} \\geq 0$ else $x*_{Bj} = 0$\"\n", "\n", "This is equivalent to the following: \n", "\n", "$((\\sum_j{x_{Bj}}=3) \\wedge (x*_{Bj} \\geq 0)) \\vee ((\\sum_j{x_{Bj}} \\leq 3) \\wedge (x*_{Bj} = 0))$\n", "\n", "where $\\wedge$ is the logical AND operator, and $\\vee$ is the logical or. That is, we want to ensure that $x*_{Bj}$ is \n", "greater than zero when $\\sum_j{x_{Bj}}=3$ or that $x*_{Bj} = 0$ when $\\sum_j{x_{Bj}} \\leq 3$. We introduce the new \n", "binary decision variable $Y$ to decide which of this two (mutually exclusive) conditions is true. Then, we multiply the \n", "binary decision variable by a very large number to render the constraints of the other condition irrelevant. \n", "\n", "We introduce the constraints: \n", "\n", "$\\sum_j{x_{Bj}} - 3 + M*Y \\geq 0$\n", "\n", "$x*_{Bj} + M*Y \\geq 0 \\quad \\forall j$\n", "\n", "These constraints correspond to the left side of the $\\vee$ operator.\n", "\n", "Similarly, to account for the right hand side, we introduce the constraints: \n", "\n", "$\\sum_j{x_{Bj}} - 3 \\leq M*(1-Y)$\n", "\n", "$x*_{Bj} \\leq M*(1-Y) \\quad \\forall j$\n", "\n", "Note that, if Y = 0, the logical constraints become: \n", "\n", "$\\sum_j{x_{Bj}}\\leq 3$\n", "\n", "$\\sum_j{x_{Bj}} - 3 \\geq 0$ (and as per the previous constraint, the sum can only be equal to 3). \n", "\n", "$x*_{Bj} \\geq 0 \\quad \\forall j$\n", "\n", "$\\sum_j{x_{Bj}} - 3 \\leq M$ (irrelevant because M is a really large number)\n", "\n", "$x*_{Bj} \\leq M \\quad \\forall j$ (irrelevant because M is a really large number)\n", "\n", "Whereas if Y = 1, the logical constraints become:\n", "\n", "$\\sum_j{x_{Bj}}\\leq 3$\n", "\n", "$\\sum_j{x_{Bj}} - 3 + M \\geq 0$ (irrelevant because M is a really large number)\n", "\n", "$x*_{Bj} + M \\geq 0 \\quad \\forall j$ (irrelevant because M is a really large number)\n", "\n", "$\\sum_j{x_{Bj}} - 3 \\leq 0$ (this is the same as the previous constraint, so also irrelevant)\n", "\n", "$x*_{Bj} \\leq 0 \\quad \\forall j$ (and since they cannot be negative, they must be equal to zero)\n", "\n", "Since the constraint $\\sum_j{x_{Bj}} - 3 \\leq M*(1-Y)$ is irrelevant when Y=0 and when Y=1, it is removed, and we get the\n", "set of constraints in the solution above.\n", "\n", "## Solution in Python\n", "The following script solves the problem using Python. \n", "### Requirements\n", "First, install the requirements:\n", " " ] }, { "cell_type": "code", "execution_count": null, "outputs": [], "source": [ "!pip install pulp\n", "!pip install pandas\n", "!pip install IPython" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": null, "outputs": [], "source": [ "import pulp\n", "import pandas as pd\n", "#And we will use numpy to perform array operations\n", "import numpy as np\n", "#We will use display and Markdown to format the output of code cells as Markdown\n", "from IPython.display import display, Markdown\n", "\n", "# Warehouses and dictionaries\n", "plants = ('A', 'B', 'C')\n", "warehouses = ('X', 'Y', 'Z')\n", "#Transportation costs\n", "transportation_costs = [[50, 60, 30], [60, 40, 20], [40, 70, 30]]\n", "\n", "# Instantiate model\n", "model = pulp.LpProblem(\"Transport Planning\", pulp.LpMinimize)\n", "\n", "# Demand\n", "demand = [5, 4, 3]\n", "\n", "# Capacities\n", "capacities = [8, 5, 3]\n", "\n", "variables = pulp.LpVariable.dicts(\"x\",\n", " [(i, j) for i in plants for j in warehouses],\n", " lowBound=0,\n", " cat='Integer')\n", "\n", "model += (\n", " pulp.lpSum([\n", " transportation_costs[i][j] * variables[(plants[i], warehouses[j])]\n", " for i in range(len(plants)) for j in range(len(warehouses))])\n", " ), \"Transportation Cost\"\n", "\n", "\n", "# Capacity constraints\n", "for i in range(len(plants)):\n", " model += pulp.lpSum([\n", " variables[(plants[i], warehouses[j])]\n", " for j in range(len(warehouses))]) <= capacities[i], plants[i]\n", "\n", "# Demand\n", "for j in range(len(warehouses)):\n", " model += pulp.lpSum([\n", " variables[(plants[i], warehouses[j])]\n", " for i in range(len(plants))]) >= demand[j], warehouses[j]" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "import pulp\n", "import pandas as pd\n", "#And we will use numpy to perform array operations\n", "import numpy as np\n", "#We will use display and Markdown to format the output of code cells as Markdown\n", "from IPython.display import display, Markdown\n", "\n", "# Warehouses and dictionaries\n", "plants = ('A', 'B', 'C')\n", "warehouses = ('X', 'Y', 'Z')\n", "#Transportation costs\n", "transportation_costs = [[50, 60, 30], [60, 40, 20], [40, 70, 30]]\n", "\n", "# Instantiate model\n", "model = pulp.LpProblem(\"Transport Planning\", pulp.LpMinimize)\n", "\n", "# Demand\n", "demand = [5, 4, 3]\n", "\n", "# Capacities\n", "capacities = [8, 5, 3]\n", "\n", "variables = pulp.LpVariable.dicts(\"x\",\n", " [(i, j) for i in plants for j in warehouses],\n", " lowBound=0,\n", " cat='Integer')\n", "\n", "model += (\n", " pulp.lpSum([\n", " transportation_costs[i][j] * variables[(plants[i], warehouses[j])]\n", " for i in range(len(plants)) for j in range(len(warehouses))])\n", " ), \"Transportation Cost\"\n", "\n", "\n", "# Capacity constraints\n", "for i in range(len(plants)):\n", " model += pulp.lpSum([\n", " variables[(plants[i], warehouses[j])]\n", " for j in range(len(warehouses))]) <= capacities[i], plants[i]\n", "\n", "# Demand\n", "for j in range(len(warehouses)):\n", " model += pulp.lpSum([\n", " variables[(plants[i], warehouses[j])]\n", " for i in range(len(plants))]) >= demand[j], warehouses[j]" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimal\n", "460.0\n" ] } ], "source": [ "# Solve our problem\n", "model.solve()\n", "print(pulp.LpStatus[model.status])\n", "\n", "# Solution\n", "max_z = pulp.value(model.objective)\n", "print(max_z)" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Solution
WarehousesXYZ
Plants
A2.00.02.0
B0.04.01.0
C3.00.00.0
\n", "
" ], "text/plain": [ " Solution \n", "Warehouses X Y Z\n", "Plants \n", "A 2.0 0.0 2.0\n", "B 0.0 4.0 1.0\n", "C 3.0 0.0 0.0" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "var_df = pd.DataFrame.from_dict(variables, orient=\"index\",\n", " columns = [\"Variables\"], dtype=object)\n", "\n", "var_df[\"Solution\"] = var_df[\"Variables\"].apply(lambda item: item.varValue)\n", "index = pd.MultiIndex.from_product([plants, warehouses], names=['Plants', 'Warehouses'])\n", "var_df2 = pd.DataFrame(var_df[\"Solution\"], index=index, columns = [\"Solution\"])\n", "display(var_df2.unstack())" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.4" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 2 }